#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
using namespace std;
class UnionFindSet
{
public:
	UnionFindSet(size_t n)
		:_ufs(n, -1)
	{}
	int FindRoot(int x)
	{
		int index = x;
		while (_ufs[index] >= 0)
		{
			index = _ufs[index];
		}
		return index;
	}
	bool Union(int x, int y)
	{
		int xroot = FindRoot(x);
		int yroot = FindRoot(y);
		if (xroot == yroot)
		{
			return false;
		}
		_ufs[xroot] += _ufs[yroot];
		_ufs[yroot] = xroot;
		return true;
	}
	int SetSize()
	{
		int count = 0;
		for (int i = 0;i < _ufs.size();++i)
		{
			if (_ufs[i] < 0) ++count;
		}
		return count;
	}
private:
	vector<int> _ufs;
};
class Solution {
public:
	bool equationsPossible(vector<string>& equations)
	{
		UnionFindSet ufs(26);
		for (int i = 0;i < equations.size();i++)
		{
			if (equations[i][1] == '=')
			{
				ufs.Union(equations[i][0] - 'a', equations[i][3] - 'a');
			}
		}
		for (int i = 0;i < equations.size();i++)
		{
			if (equations[i][1] == '!')
			{
				auto x = ufs.FindRoot(equations[i][0] - 'a');
				auto y = ufs.FindRoot(equations[i][3] - 'a');
				if (x == y) return false;
			}
		}
		return true;
	}
};